package leetcode.数学;

import java.util.ArrayList;

/**
 * 康托展开：给出 52413 求它是 [1,2,3,4,5] 全排列里面的第几个数
 * <p>
 * 逆康托展开：给出 [1,2,3,4,5] 求第 107 个排列是什么数
 * 应用题：
 * 1. Test60
 */
public class 逆康托展开 {

    public static void main(String[] args) {
        System.out.println(inverseCantorExpansion(5, 107));//52413
        System.out.println(inverseCantorExpansion(8, 27));// 12354768
    }

    /**
     * 给出 [1,2,3,...,n] 数组以及该数组全排列的第 K 个序列编号，求第 K 个数是啥
     *
     * @param n 数组的最大值
     * @param k 序号
     * @return 第K个数的值
     */
    public static String inverseCantorExpansion(int n, int k) {
        // 先搞一个1~n的数组，用来在里面选择合适的数字加入 ans 中
        ArrayList<Integer> array = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            array.add(i + 1);
        }

        StringBuilder ans = new StringBuilder();
        k -= 1;

        // 执行 n 次循环得到 n 个数，组合成一个答案
        for (int i = 0; i < n; i++) {
            // 计算从 (n-1)! 开始的阶乘
            int Xfactorial = getFactorial(n - i - 1);
            // 计算获取数组的那一个位置的数字
            int index = k / Xfactorial;
            // 获取该数字
            ans.append(array.get(index));
            // 更新 k 为上一次除法计算的余数
            k %= Xfactorial;
            // 同时更新数组，删除已经获得过的数字
            array.remove(index);
        }
        return ans.toString();
    }

    // 求x的阶乘
    public static int getFactorial(int x) {
        if (x == 0)
            return 1;
        int res = x;
        for (int i = 1; i < x; i++) {
            res *= i;
        }
        return res;
    }


}
